package newcoder_exp.justPractise;

import org.junit.Test;

public class NC87 {
    public class Solution {
        // 扔棋子（鸡蛋）问题
        /*
         * 0 ~ N层，第0层绝对不会碎。求使用k个鸡蛋探测n层楼中，尝试的**最差情况下的最少探测次数**
         * 最差：即尝试不是随机的，所得到结果的尝试次数肯定是我此时尝试方案的最后一次测试中得到结果；
         * 如，只有一个鸡蛋，探测n层楼，那就必须探测n次【即每次探测只能测试一次，之后探测结束
         * 即每层都需要测试一次】《探测1次的意思是花光所有的鸡蛋所能得到的信息，测试1次的 意思是仍一个鸡蛋所得到的信息，测试1次是探测1次的一个小步骤】
         * 
         * 最少：即实际的探测方案最好，每次落点都在最好的那个方案上的每一个最优的测试步骤。
         * 
         * =============================================================================
         * ==============================
         * 
         * 没有数学上的规律，借助于枚举：
         * 
         * 设f[i][j]为使用j个鸡蛋来探测i层楼中最优方案的尝试最多进行的次数。
         * 假设扔第j个鸡蛋在第i层没有碎，那么接下来只需要使用这j个鸡蛋探测楼上剩下的层即可，即f[n - i][j]
         * 假设碎了，鸡蛋数量少了一个，而探测的楼层也变成了楼下的i-1层，即f[i-1][j-1]
         * 由于在i层丢的这个鸡蛋也是一次测试次数，最终要求的在第i层丢导致的最差的结果就是max(f[n-i][j],f[i-1][j-1])+1
         * 我们需要枚举出来的就是一种最优的解决方案，即每一次尝试都是在未知的求解楼层中选择一个最好的楼层去丢，因此i需要通过枚举出来 即F =
         * min(max(f[n-i][j],f[i-1][j-1])+1) 【i∈[1,n-1]】
         * 
         * 边界条件：f[i][1] = i; 只有一个鸡蛋，只能逐一尝试 f[i][0] = 0; 无法尝试 f[0][j] = 0; 确定第0层不会碎。
         * f[1][j] = 1; 只有一层楼，也只需要尝试一次。
         */
        public int solve1(int n, int k) {
            int[][] f = new int[n + 1][k + 1];
            // f[i][j]有一个为0，默认为0
            for (int i = 1; i <= n; i++) {
                f[i][1] = i;
            }
            for (int j = 1; j <= k; j++) {
                f[1][j] = 1;
            }

            int t;
            for (int i = 2; i <= n; i++) {
                for (int j = 2; j <= k; j++) {
                    f[i][j] = Integer.MAX_VALUE;
                    for (int g = 1; g <= i; g++) {
                        t = Math.max(f[g - 1][j - 1], f[i - g][j]) + 1; // 选择1~i-1中一个层丢鸡蛋
                        f[i][j] = Math.min(t, f[i][j]);
                    }
                }
            }

            return f[n][k];
        }

        // 上面的解法内存溢出
        /*
         * 优化空间：鸡蛋数量只与这一层与上一层有关 可以使用**两个一维数组**存储这两层的状态。
         */

        public int solve(int n, int k) {
            int[] l = new int[n + 1];
            int[] f = new int[n + 1];
            int[] temp;
            // f[i][j]有一个为0，默认为0
            for (int i = 1; i <= n; i++) {
                f[i] = i;
            }

            int t;
            for (int i = 2; i <= n; i++) {
                temp = new int[n + 1];
                System.arraycopy(f, 0, temp, 0, n + 1);
                for (int j = 2; j <= k; j++) {
                    f[i] = Integer.MAX_VALUE;
                    for (int g = 1; g <= i; g++) {
                        t = Math.max(f[n - g], l[g - 1]) + 1;
                        f[i] = Math.min(f[i], t);
                    }
                }
                l = temp;
            }

            return f[n];
        }

        public

                int getMinSteps(int eggNum, int floorNum) {

            if (eggNum < 1 || floorNum < 1) {

                return

                0;

            }

            // 上一层备忘录，存储鸡蛋数量-1的floorNum层楼条件下的最优化尝试次数

            int[] preCache = new

            int[floorNum + 1];

            // 当前备忘录，存储当前鸡蛋数量的floorNum层楼条件下的最优化尝试次数

            int[] currentCache = new

            int[floorNum + 1];

            // 把备忘录每个元素初始化成最大的尝试次数

            for (int i = 1; i <= floorNum; i++) {

                currentCache[i] = i;

            }

            for (int n = 2; n <= eggNum; n++) {

                // 当前备忘录拷贝给上一次备忘录，并重新初始化当前备忘录

                preCache = currentCache.clone();

                for (int i = 1; i <= floorNum; i++) {

                    currentCache[i] = i;

                }

                for (int m = 1; m <= floorNum; m++) {

                    for (int k = 1; k < m; k++) {

                        // 扔鸡蛋的楼层从1到m枚举一遍，如果当前算出的尝试次数小于上一次算出的尝试次数，则取代上一次的尝试次数。

                        // 这里可以打印k的值，从而知道第一个鸡蛋是从第几次扔的。

                        currentCache[m] = Math.min(currentCache[m], 1 + Math.max(preCache[k - 1], currentCache[m - k]));

                    }

                }

            }

            return currentCache[floorNum];

        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // int res = s.solve(1000000, 1000000);
        int res = s.getMinSteps(1000000,1000000);
        System.out.println(res);
    }
}
